package 高级班;

public class split_num {
    public static int ways1(int n) {
        if (n < 1) {
            return 0;
        }
        return process(1, n);
    }


    public static int process(int pre, int rest) {
        if (rest == 0) {
            return 1;
        }
        if (pre > rest) {
            return 0;
        }
        int ways = 0;
        for (int i = pre; i <= rest; i++) {
            ways += process(i, rest - i);
        }
        return ways;
    }


    public static int ways2(int n) {
        if (n < 1) {
            return 0;
        }
        int[][] dp = new int[n + 1][n + 1];
        for (int pre = 1; pre < dp.length; pre++) {
            dp[pre][0] = 1;
        }
        for (int pre = n; pre > 0; pre--) {
            for (int rest = pre; rest <= n; rest++) {
                for (int i = pre; i <= rest; i++) {
                    dp[pre][rest] += dp[i][rest - i];
                }
            }
        }
        return dp[1][n];
    }


    public static int ways3(int n) {
        if (n < 1) {
            return 0;
        }
        int[][] dp = new int[n + 1][n + 1];
        for (int pre = 1; pre < dp.length; pre++) {
            dp[pre][0] = 1;
        }
        for (int pre = 1; pre < dp.length; pre++) {
            dp[pre][pre] = 1;
        }
        for (int pre = n - 1; pre > 0; pre--) {
            for (int rest = pre + 1; rest <= n; rest++) {
                dp[pre][rest] = dp[pre + 1][rest] + dp[pre][rest - pre];
            }
        }
        return dp[1][n];
    }

    //ytc
    public static int process(int num){
        if (num<1)
            return 0;
        return f(1,num);
    }
    public static int f(int pre,int rest){
        if (rest==0)
            return 1;
        if (pre>rest)
            return 0;
        int ways=0;
        for (int i=pre;i<=rest;i++){
            ways+=f(i,rest-i);
        }
        return ways;
    }

    public static int dp_ytc(int num){
        int[][] dp=new int[num+1][num+1];
        for (int i=1;i<num+1;i++)
            dp[i][0]=1;
        for (int i=num;i>0;i--){
            for (int j=i;j<=num;j++){
                for (int k=i;k<=j;k++)
                    dp[i][j]+=dp[k][j-k];
            }
        }
        return dp[1][num];

    }
    public static int dp_ytc2(int num){
        int[][] dp=new int[num+1][num+1];
        for (int i=1;i<num+1;i++)
            dp[i][0]=1;
        for (int i=1;i<num+1;i++)
            dp[i][i]=1;
        for (int i=num-1;i>0;i--){
            for (int j=i;j<=num;j++){
                dp[i][j]=dp[i+1][j]+dp[i][j-i];
            }
        }
        return dp[1][num];
    }


    public static void main(String[] args) {
        int n = 20;
        System.out.println(ways1(n));
        System.out.println(ways2(n));
        System.out.println(ways3(n));
        //ytc
        System.out.println(process(n));
        System.out.println(dp_ytc(n));
        System.out.println(dp_ytc2(n));
    }
}
